1. Field of Invention
The present invention relates generally to the field of database query optimization. More specifically, the present invention is related to a hybrid analytical and statistical learning approach to query operator cost estimation.
2. Discussion of Prior Art
Developing cost models for query optimization is significantly harder for XML queries than for traditional relational queries. This is because XML query operators are much more complex than relational operators such as table scans and joins. Management of XML data, especially the processing of XPath queries, has been the focus of considerable research and development activity over the past few years. A wide variety of join-based, navigational, and hybrid XPath processing techniques are now available. Each of these techniques can exploit indices that are either structural, value-based, or both. An XML query optimizer can therefore choose among a large number of alternative plans for processing a specified XPath expression. As in the traditional relational database setting, the optimizer needs accurate cost estimates for the XML operators in order to choose a good plan.
Unfortunately, developing cost models of XML query processing is much harder than developing cost models of relational query processing. Relational query plans can be decomposed into a sequence of relatively simple atomic operations such as table scans, nested-loop joins, and so forth. The data access patterns for these relational operators can often be predicted and modeled in a fairly straightforward way. Complex XML query operators such as TurboXPath and holistic twig join, on the other hand, do not lend themselves to such a decomposition. The data access patterns tend to be markedly non-sequential and therefore quite difficult to model. For these reasons, the traditional approach of developing detailed analytic cost models based on a painstaking analysis of the source code often proves extremely difficult. Such an analysis is also particularly difficult for an XML query, more so than for a relational query. Cost estimation is similarly difficult for queries with user-defined functions (UDFs) and in multiple databases systems. In this latter setting, some researchers have proposed replacing analytic cost models with statistical learning models that estimate the cost of processing a query based on the input features of the query and data. Input features are chosen on the basis of those features that appear most likely to affect the cost of processing a query.
In the setting of user-defined functions (UDFs), features are often fairly obvious; for example, the values of the arguments to the UDF, or perhaps some simple transformations of these values. In the multiple database setting, determining features becomes more complicated. In the XML setting, feature identification becomes even more complex. The features that have the greatest impact on the cost of executing a query or query operator tend to be “posterior” features; for example, the number of data objects returned and the number of candidate results inserted in an in-memory buffer. These depend on the data and cannot be observed until after the operator has finished executing. Thus, there is a need in the art for estimating values for posterior input features to a query operator.
The motivation for the XML query optimization problem is first discussed and subsequently, an overview of one typical XML query operator, called XNav, is given. Consider the following FLWOR expression, which finds the titles of all books having at least one author named “Stevens” and published after 1991.
<bib>  {  for $b in doc(“bib.xml”)/bib/book  where $b/authors//last = “Stevens” and    $b/@year > 1991  return    <book>      { $b/title }    </book>  }</bib>The three path expressions in the for- and where- clauses constitute the matching part, and the return clause corresponds to the construction part. In order to answer the matching part, an XML query processing engine may generate at least three query plans: navigate the bib.xml document down to find all book elements under the root element bib and, for each such book element, evaluate the two predicates by navigating down to the attribute year and element last under authors; find the elements with the values “Stevens” or “1991” through value-based indexes, then navigate up to find the parent/ancestor element book, verify other structural relationships, and finally check the remaining predicate; or find, using a twig index, all tree structures in which last is a descendant of authors, book is a child of bib, and @year is an attribute of book and then for each book, check the two value predicates.
Any one of these plans can be the best plan, depending on the circumstances. To compute the cost of a plan, the optimizer estimates the cost of each operator in the plan—in this example, the index access operator, the navigation operator, and the join operator and then combines their costs using an appropriate formula. For example, let p1, p2, and p3 denote the path expressions doc(“bib.xml”)/bib/book, authors//last[.=“Stevens”], and @year[.>1991], respectively. The cost of the first plan above may be modeled by the following formula:costnv(p1)+|p1|×costnv(p2)+|p1[p2]|×costnv(p3),where costnv(p) denotes the estimated cost of evaluating the path expression p by the navigational approach, and |p| denotes the cardinality of path expression p. Therefore, it is shown that costing of path-expression evaluation is crucial to the costing of alternative query plans, and thus to choosing the best plan.
One navigational XML operator that has been proposed to illustrate the methodology of the present invention is the XNav operator, which is a slight adaptation of the stream-based TurboXPath algorithm as applied to pre-parsed XML stored as paged trees. It is emphasized, however, that the general methodology of the present invention is applicable to both XML and relational query operators. As with TurboXPath, the XNav algorithm processes the path query using a single-pass, pre-order traversal of the document tree. Unlike TurboXPath, which copies the content of the stream, XNav manipulates XML tree references, and returns references to all tree nodes that satisfy a specified input XPath expression. Another difference between TurboXPath and XNav is that, when traversing the XML document tree, XNav skips those portions of the document that are not relevant to the query evaluation. This behavior makes the cost modeling of XNav highly challenging. XNav behaves in a manner as approximated by the algorithm shown in FIG. 1.
Given a parse tree representation of a path expression and an XML document, XNav matches the incoming XML elements with the parse tree while traversing the XML data in document order. An XML element matches a parse-tree node if (1) the element name matches the node label, (2) the element value satisfies the value constraints if the node is also a predicate tree node, and (3) the element satisfies structural relationships with other previously matched XML elements as specified by the parse tree. An example of the parse tree is shown in FIG. 2. It represents the path expression /bib/book[authors//last=“Stevens”][@year>1991]/title. In this parse tree, each unshaded node corresponds to a “NodeTest” in the path expression, except that the node labeled “r” is a special node representing the starting node for the evaluation, which can be the document root or any other internal node of the document tree. The doubly-circled node is the “output node”. Each NodeTest with a value constraint (i.e., a predicate) has an associated predicate tree. These are shaded in FIG. 2. Edges between parse tree nodes represent structural relationships (i.e., axes). Solid and dashed lines represent child (“/”) and descendant (“//”) axes, respectively. Each predicate is attached to an “anchor node” (book in the example) that represents the XPath step at which the predicate appears.
For brevity and simplicity, only path those expressions containing / and //-axes, wildcards, branching, and value-predicates are considered.